package architect.algorithn;

/**
 * 猴子吃桃
 *
 * @author guanxin
 * @date 2018/5/8 9:02
 */

public class Monkey {
    //猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾就多吃了一个。第二天早上又将剩下的桃子吃了一半，还是不过瘾又多
    //
    //吃了一个。以后每天都吃前一天剩下的一半再加一个。到第10天刚好剩一个。问猴子第一天摘了多少个桃子？

    public static void main(String[] args) {
        int sum1 = recursion(0);
        int sum2 = recursionTail(10, 1);
        int sum3 = circulation(10);

        System.out.printf("\"第一天摘得桃子：%d个", sum3);
    }

    // 普通递归
    private static int recursion(int days) {
        if (days == 10)
            return 1;

        return 2 * recursion(days + 1) + 2;
    }

    // 尾递归
    private static int recursionTail(int days, int total) {
        if (days == 0)
            return total;

        return recursionTail(days - 1, 2 * total + 2);
    }

    // 循环
    private static int circulation(int days) {
        int sum = 1;
        for (int i = 1; i <= days; i++) {
            sum = 2 * sum + 2;
        }
        return sum;
    }
}
